/**
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串
 
 
示例1：
输入："dp"
输出：2
解释：共有两个回文子串，分别为 "d", "p"。



示例2：

输入："aaa"
输出：6
解释：共有六个回文子串，分别为 "a", "a", "a", "aa", "aa", "aaa"。注意题设，具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串，因此像 "aa" 和 "aa" 就是两个不同的回文子串。
 

f(i,j) = f(i+1,j-1) && (Si=Sj);  
 */


int countSubstrings(String s) {
    int n = s.length();
    if (0 == n) return 0;

    int ans = 0;
    boolean[][] dp = new boolean[n][n];

    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        ans++;
    }

    for (int j = 1; j < n; j++) {
        for (int i = 0; i < j; i++) {
            dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j-i <3 || dp[i+1][j-1]);
            if (dp[i][j]) {
                 ans++; 
            }
        }
    }

    return ans;
}


/**
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000。


示例1：

输入："asssasms"
输出：5
解释：一个可能的最长回文子序列为 "sssss"，另一种可能的答案是 "asssa"。


示例2：

输入："abba"
输出：4
解释：有三个子序列满足题设要求："aa"、"bb" 和 "abba"，因此答案为 4。
**/


int getLongestPalindromeSubseq(String s) {
    int n = s.length(); if (0 == n) return 0;

    int[][] dp = new int[n][n]; 
    for (int[] row : dp) { Arrays.fill(row, 0); }
    for (int i = 0; i < n; i++) dp[i][i] = 1; // 初始化状态

    for (int i = n-1; i >= 0; i--) {
        for (int j = i+1; j < n; j++) {
            if (s.charAt(i)==s.charAt(j)) {
                dp[i][j] = 2 + dp[i+1][j-1];
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); // 作出进一步决策
            }
        }
    }

    return dp[0][n-1]; // 输出答案
}